package com.nine.algorithm.queue;

import java.util.Iterator;

/**
 * @author nine
 * @version 1.0
 * @description 构建单向环形链表
 * @date 24/5/8 23:19
 */
public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {

	private static class Node<E> {
		private E value;

		private Node<E> next;

		public Node(E value, Node<E> next) {
			this.value = value;
			this.next = next;
		}
	}

	private Node<E> head = new Node<>(null, null);

	private Node<E> tail = head;

	private int size;   // 节点数

	private int capacity = Integer.MAX_VALUE;    // 容量

	{
		tail.next = head;
	}

	public LinkedListQueue() {
		// 初始化共性代码抽取放到外面
		// tail.next = head;
	}

	public LinkedListQueue(int capacity) {
		this.capacity = capacity;

	}

	@Override
	public boolean offer(E value) {

		if (isFull()) {
			return false;
		}

		// 新增的元素，指向头节点
		Node<E> added = new Node<>(value, head);
		// 将tail的next指向新增的元素
		tail.next = added;

		// tail元素最终指向新增的元素
		tail = added;
		size++;
		return true;
	}

	/**
	 * 从队列头获取值，并移除
	 *
	 * @return 如果队列非空，返回对头值，否则null
	 */
	@Override
	public E poll() {
		if (isEmpty()) {
			return null;
		}
		Node<E> first = head.next;
		head.next = first.next;
		// 第一个节点就是tail的话，移除时，需要将tail移到head节点
		if (first == tail) {
			tail = head;
		}
		size--;
		return first.value;
	}


	/**
	 * 从队列头获取值，不移除
	 *
	 * @return 如果队列非空，返回对头值，否则null
	 */
	@Override
	public E peek() {
		if (isEmpty()) {
			return null;
		}
		return head.next.value;
	}

	@Override
	public boolean isEmpty() {
		return head == tail;
	}

	/**
	 * 检查队列是否已满
	 *
	 * @return 满，返回true，否则false
	 */
	@Override
	public boolean isFull() {
		return size == capacity;
	}

	@Override
	public Iterator<E> iterator() {
		return new Iterator<E>() {
			Node<E> p = head.next;

			@Override
			public boolean hasNext() {
				// 节点不是头节点时，继续循环
				return p != head;
			}

			@Override
			public E next() {
				E value = p.value;
				p = p.next;
				return value;
			}
		};
	}
}
